package q78_subsets;

import java.util.ArrayList;
import java.util.List;

public class Solution_2 {

    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> bin = new ArrayList<>();
    /**
     * 使用模板的解法
     */
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    /**
     * 在子集问题中与之前的问题所存在的区别，此前我们对于结果的添加均为在if判断中进行
     * 而对于子集问题，则应该放在dfs的最开始进行，原因在于：
     * 对于所有的子集，其对应的是我们在树上的每一个节点，而不是像之前只是在树的末端叶子节点进行判断
     * 所以我们要dfs的开始就判断每一个树上的节点是否已经满足了题目要求，并添加到结果中
     * 此题仅仅需要将所有节点加入其中，所以不需要过多判读
     */
    private void dfs(int[] nums, int start) {
        // 特殊点 子集的添加要在最上面 否则会漏掉单个元素本身
        res.add(new ArrayList<>(bin));

        // 终止条件
        if (start >= nums.length){
            return;
        }

        for (int i = start; i < nums.length; i++) {
            bin.add(nums[i]);

            dfs(nums, i + 1);

            bin.remove(bin.size() - 1);
        }

    }
}
